﻿#include "RecursiveDFSMultipleCycleFinderAlgorithm.h"

using namespace analyzer;

#include "FileType.h"
#include "string.h"

RecursiveDFSMultipleCycleFinderAlgorithm::RecursiveDFSMultipleCycleFinderAlgorithm(void)
{
	failOnFirst = false;
}

RecursiveDFSMultipleCycleFinderAlgorithm::~RecursiveDFSMultipleCycleFinderAlgorithm(void)
{
	// empty destrcutor
}

std::vector<std::vector<int> > RecursiveDFSMultipleCycleFinderAlgorithm::findCycle(const Graph& graph) {
 
	boost::graph_traits<Graph>::vertex_iterator vi, vi_end;
	
	std::vector<VertexColor> colors(boost::num_vertices(graph) , white);
	
	parentVertexMap.clear();
	cyclicVertices.clear();
	
	boost::property_map<Graph, vertex_type_t>::type vertexTypes = boost::get(vertex_type_t(), const_cast<Graph&>(graph));
	
	boost::property_map<Graph, boost::vertex_name_t>::type vertexNames = boost::get(boost::vertex_name_t(), const_cast<Graph&>(graph));
	
	for (tie(vi, vi_end) = boost::vertices(graph) ; vi != vi_end; ++vi) {
		if (boost::get(vertexTypes, *vi) == SOURCE_FILE && colors[*vi] == white) {
			findCycleDFS(graph, *vi, colors);
		}
	}

	return cyclicVertices;
}

void RecursiveDFSMultipleCycleFinderAlgorithm::findCycleDFS(const Graph& graph, Vertex u, std::vector<VertexColor>& colors)
{ 
	boost::graph_traits<Graph>::adjacency_iterator vi, vi_end;
	
	colors[u] = gray;
	
	for (boost::tie(vi, vi_end) = boost::adjacent_vertices(u, graph) ; vi != vi_end; ++vi) {
		if (colors[*vi] == white) {
			parentVertexMap.insert(std::pair<Vertex, Vertex>(*vi, u));
			findCycleDFS(graph, *vi, colors);
		}
		else if (colors[*vi] == gray) {
			cyclicVertices.push_back(getCyclicVertices(*vi, u, parentVertexMap));
			
			// TODO this is the place when the algorithm can be stoped
		}
	}
	
	// TODO this is the most problematic instruction to make the whole algorithm iterative
	colors[u] = black;
}

std::vector<int> RecursiveDFSMultipleCycleFinderAlgorithm::getCyclicVertices(Vertex searchVertex, Vertex startVertex, std::map<Vertex, Vertex> parentVertexMap) {

	std::vector<int> result;
	Vertex u = startVertex;

	result.push_back(searchVertex);

	do {
		result.push_back(u);
	} while((u = parentVertexMap[u]) != searchVertex && u != result.back());

	result.push_back(searchVertex);

	return result;
}

bool RecursiveDFSMultipleCycleFinderAlgorithm::getFailOnFirst() const {

	return failOnFirst;
}

void RecursiveDFSMultipleCycleFinderAlgorithm::setFailOnFirst(bool failOnFirst) {

	this -> failOnFirst = failOnFirst;
}
